import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-24
 * Time: 23:18
 */
public class Solution {
    public int equalPairs(int[][] grid) {
        int ans = 0;
        int len = grid.length;
        // 将列转换为 行
        int[][] col = new int[len][len];
        for (int i = 0;i < len;i++) {
            for (int j = 0;j < len;j++) {
                col[i][j] = grid[j][i];
            }
        }
        // 进行匹配, 时间复杂度 O(n^3)
        for (int i = 0;i < len;i++) {
            for (int j = 0;j < len;j++) {
                if (Arrays.equals(grid[i], col[j])) {
                    ans++;
                }
            }
        }
        return ans;
    }


    /**
     *  方法二: 将每行用拼接成字符串, 注意加上一个分隔符, 不然出错
     *  时间复杂度为 O(n ^ 2)
     * @param grid
     * @return
     */
    public int equalPairs2(int[][] grid) {
        int ans = 0;
        HashMap<String, Integer> map = new HashMap<>();
        int len = grid.length;
        for (int i = 0;i < len;i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0;j < len;j++) {
                // 注意加上一个分隔符, 不然出错
                stringBuilder.append(grid[i][j]).append(".");
            }
            String s = stringBuilder.toString();
            map.put(s, map.getOrDefault(s, 0)+1);
        }

        for (int i = 0;i < len;i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0;j < len;j++) {
                // 注意加上一个分隔符, 不然出错
                stringBuilder.append(grid[j][i]).append(".");
            }
            String s = stringBuilder.toString();
            ans += map.getOrDefault(s, 0);
        }

        return ans;
    }


    /**
     *  方法三: 与方法二实际是差不多的, 方法二是将拼接成的字符串作为 key,
     *  方法三是将对应的集合作为 key
     * @param grid
     * @return
     */
    public int equalPairs3(int[][] grid) {
        int n = grid.length;
        Map<List<Integer>, Integer> cnt = new HashMap<List<Integer>, Integer>();
        for (int[] row : grid) {
            List<Integer> arr = new ArrayList<Integer>();
            for (int num : row) {
                arr.add(num);
            }
            cnt.put(arr, cnt.getOrDefault(arr, 0) + 1);
        }

        int res = 0;
        for (int j = 0; j < n; j++) {
            List<Integer> arr = new ArrayList<Integer>();
            for (int i = 0; i < n; i++) {
                arr.add(grid[i][j]);
            }
            if (cnt.containsKey(arr)) {
                res += cnt.get(arr);
            }
        }
        return res;
    }
}
